// AutoFiller.cpp: implementation of the CAutoFiller class.
//
//////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "AutoFiller.h"
#include <memory.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#ifndef _countof
#define _countof(A) (sizeof(A)/sizeof(A[0]))
#endif	// _countof

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CCheckInContour::CCheckInContour()
{
	m_nMaxX = 0;
	m_nMaxY = 0;
	m_pContour = NULL;
	m_nContour = 0;

	m_dy = 0;
	m_pInFlag = NULL;
}

CCheckInContour::~CCheckInContour()
{
	freeMemory();
}

/////////////////////////////////////////////////////////////////////

int CCheckInContour::setMaxSize(int cx, int cy)
{
	ASSERT(this != NULL);
	m_nMaxX = cx;
	m_nMaxY = cy;
	m_dy = 0;
	freeMemory();
	return 0;
}

int CCheckInContour::setContour(const SPoint *lpPoint, int nPoint)
{
	ASSERT(this != NULL);
	m_pContour = lpPoint;
	m_nContour = nPoint;
	m_dy = 0;
	freeMemory();
	return 0;
}

BOOL CCheckInContour::inContour(int x, int y)
{
	ASSERT(this != NULL);
	// check arguments
	if (x<0 || x>=m_nMaxX || y<0 || y>=m_nMaxY)
		return FALSE;
	// select a guide direction
	if (m_dy == 0)
		initContourCheck();
	// for low memory case
	if (!m_pInFlag)
		return checkPointInContour(x, y);
	// typical case
	BOOL fIn;
	BYTE b = m_pInFlag[m_nMaxX * y + x];
	switch(b) {
	case 0:
		// unknown, check it once
		fIn = checkPointInContour(x, y);
		m_pInFlag[m_nMaxX * y + x] = (BYTE)(fIn ? 0x01 : 0xff);
		break;
	case 1:
		// in contour
		fIn = TRUE;
		break;
	default:
		// not in
		fIn = FALSE;
		break;
	}
	return fIn;
}

int CCheckInContour::freeMemory(void)
{
	ASSERT(this != NULL);
	if (m_pInFlag != NULL) {
		delete[] m_pInFlag;
		m_pInFlag = NULL;
	}
	return 0;
}

int CCheckInContour::getContour(const SPoint **ppPoint)
{
	ASSERT(this != NULL);
	*ppPoint = m_pContour;
	return m_nContour;
}

/////////////////////////////////////////////////////////////////////

BOOL CCheckInContour::initContourCheck(void)
{
	int m;
	// to select a guide direction
	for(m_dy=0; m_dy<m_nContour; m_dy++) {
		BOOL fZero = FALSE;
		for(int i=0; !fZero && i<m_nContour; i++) {
			int j = (i + 1) % m_nContour;
			m = -m_dy * (m_pContour[j].x - m_pContour[i].x) + (m_pContour[j].y - m_pContour[i].y);
			if (!m)
				fZero = TRUE;
		}
		if (!fZero)
			break;
	}
	// to enable cache for checking point in contour or not
	if (!m_pInFlag) {
		if ((m_pInFlag=new BYTE[m_nMaxX * m_nMaxY]) == NULL)
			return FALSE;
	}
	memset(m_pInFlag, 0, m_nMaxX * m_nMaxY);
	return TRUE;
}

BOOL CCheckInContour::checkPointInContour(int x, int y)
{
	// count on line L: x(t) = x + t; y(t) = y + m_dy * t.
	int m0, m1, m2, k_xy, k_inf;
	int nCount = 0;
	for(int i=0; i<m_nContour; i++) {
		int j = (i + 1) % m_nContour;
		// to skip some lines
		int x0 = m_pContour[i].x;
		int y0 = m_pContour[i].y;
		int x1 = m_pContour[j].x;
		int y1 = m_pContour[j].y;
		// on the same side of line
		m0 = -m_dy * (x0 - x) + (y0 - y);
		m1 = -m_dy * (x1 - x) + (y1 - y);
		if ((m0<0 && m1<0) || (m0>0 && m1>0))
			continue;
		// to skip head point, every point should be checked only once
		if (m0 == 0)
			continue;
		if (m1 == 0) {
			// special case, convex point
			int k = (i + 2) % m_nContour;
			int x2 = m_pContour[k].x;
			int y2 = m_pContour[k].y;
			m2 = -m_dy * (x2 - x) + (y2 - y);
			if ((m0<0 && m2<0) || (m0>0 && m2>0))
				continue;
		}
		// on boundary line
		k_xy = -(y1 - y0) * (x - x0) + (x1 - x0) * (y - y0);
		if (k_xy == 0)
			return TRUE;
		// (x, y) near (0, 0), skip
		//k_inf = -(y1 - y0) + (x1 - x0) * m_dy;
		k_inf = m0 - m1;
		if ((k_xy<0 && k_inf>0) || (k_xy>0 && k_inf<0))
			continue;
		// (x, y) near (N, N * m_dy), N is very large
		nCount++;
	}
	return ( (nCount & 1) != 0 );
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
const SPoint NEIGHBOR_LIST[] = {
    {-1, -1},	{0, -1},	{1, -1},
    {-1, 0},				{1, 0},
    {-1, 1},	{0, 1},		{1, 1},
};

const SPoint NEIGHBOR_LIST2[] = {
    {0, -1}, {1, 0}, {0, 1}, {-1, 0}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1},
    {-1, -2}, {0, -2}, {1, -2}, {2, -1}, {2, 0}, {2, 1}, {1, 2}, {0, 2}, {-1, 2}, {-2, 1}, {-2, 0}, {-1, -2}
};

CAutoFiller::CAutoFiller(CCheckInContour *pCheck, BOOL fCirclrFill)
{
	m_pCheck = pCheck;
	m_pbFlag = NULL;
	m_nFlag = 0;
    
    if (fCirclrFill) {
        m_pOffset = NEIGHBOR_LIST2;
        m_nOffset = _countof(NEIGHBOR_LIST2);
    } else {
        m_pOffset = NEIGHBOR_LIST;
        m_nOffset = _countof(NEIGHBOR_LIST);
    }
}

CAutoFiller::~CAutoFiller()
{
	clear();
}

/////////////////////////////////////////////////////////////////////

BOOL CAutoFiller::resetGetPoint(int x, int y)
{
	ASSERT(this != NULL);
	ASSERT(m_pCheck != NULL);
	// to check arguments
	if (!m_pCheck->inContour(x, y))
		return FALSE;
	// to prepare memory and to clear history
	m_ptChkList.RemoveAll();
	if (!m_pbFlag) {
		int n = (m_pCheck->getMaxX() + 7) / 8;
		int nY = m_pCheck->getMaxY();
		if ((m_pbFlag = new BYTE[n * nY]) == NULL)
			return FALSE;
		m_nFlag = n * nY;
	}
	memset(m_pbFlag, 0, m_nFlag);
	// to set up candidate list
	SPoint pt = {(short)x, (short)y};
	m_ptChkList.Add(pt);
	return TRUE;
}

BOOL CAutoFiller::getNextPoint(SPoint *lpPoint, LPCheckInRange lpfnCheck, void *lpContext)
{
	ASSERT(this != NULL);
	ASSERT(m_pCheck != NULL);
	// to check candidate list, may fail
	int nSize = m_ptChkList.GetSize();
	if (nSize <= 0) {
		lpPoint->x = 0;
		lpPoint->y = 0;
		return FALSE;
	}
	// to select the head point
	SPoint pt0 = m_ptChkList[0];
	m_ptChkList.RemoveAt(0);
	// to check neighbor of this point
	addNeighborPoints(pt0, lpfnCheck, lpContext);
	*lpPoint = pt0;
	return TRUE;
}

BOOL CAutoFiller::addNeighborPoints(const SPoint& pt0, LPCheckInRange lpfnCheck, void *lpContext)
{
	SPoint pt;
	int x, y, m;
	BOOL fAddPoint = FALSE;
	int nX = m_pCheck->getMaxX();
	int nY = m_pCheck->getMaxY();
	int n = (nX + 7) / 8;
	for(int i=0; i<m_nOffset; i++) {
		x = pt0.x + m_pOffset[i].x;
		y = pt0.y + m_pOffset[i].y;
		// may out of range
		if (x<0 || x>=nX || y<0 || y>=nY)
			continue;
		// may be selected
		m = y * n + (x >> 3);
		if (m_pbFlag[m] & (1 << (x & 7)))
			continue;
		// may not in contour
		if ((lpfnCheck!=NULL && !lpfnCheck(lpContext, x, y)) || !m_pCheck->inContour(x, y))
			continue;
		// to set flag
		m_pbFlag[m] |= (1 << (x & 7));
		// append into tail
		pt.x = (short)x;
		pt.y = (short)y;
		m_ptChkList.Add(pt);
		fAddPoint = TRUE;
	}
	return fAddPoint;
}

int CAutoFiller::clear(void)
{
	ASSERT(this != NULL);
	m_pCheck->freeMemory();
	m_ptChkList.RemoveAll();
	if (m_pbFlag != NULL) {
		delete[] m_pbFlag;
		m_pbFlag = 0;
		m_nFlag = 0;
	}
	return 0;
}
